Skip to main content

Word Break

LeetCode 139 | Difficulty: Medium​

Problem Description​

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: The same word in the dictionary may be reused multiple times in the segmentation.

Constraints​

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters
  • All strings in wordDict are unique

Examples​

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse dictionary words.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Approach​

This is a classic dynamic programming problem where we check if prefixes of the string can be segmented.

DP State Definition:

  • dp[i] = true if s[0..i-1] can be segmented using words from the dictionary

Transition:

  • dp[i] = true if there exists some j < i where:
    • dp[j] == true (prefix is valid), AND
    • s[j..i-1] is in the dictionary

DP Table for "leetcode": | Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |-------|---|---|---|---|---|---|---|---|---| | Char | - | l | e | e | t | c | o | d | e | | dp[i] | T | F | F | F | T | F | F | F | T |

  • dp[0] = true (empty string is valid)
  • dp[4] = true because dp[0]=true and "leet" is in dict
  • dp[8] = true because dp[4]=true and "code" is in dict

Complexity Analysis​

  • Time Complexity: $O(N^3)$ or $O(N^2 \times K)$ — where $N$ is string length and $K$ is max word length
  • Space Complexity: $O(N)$ — for the DP array

Solution: Bottom-Up DP​

public bool WordBreak(string s, IList<string> wordDict)
{
    HashSet<string> dict = new HashSet<string>(wordDict);
    bool[] dp = new bool[s.Length + 1];
    dp[0] = true; // Empty string is valid
    
    for (int i = 1; i <= s.Length; i++)
    {
        for (int j = 0; j < i; j++)
        {
            // If prefix s[0..j-1] is valid AND s[j..i-1] is in dictionary
            if (dp[j] && dict.Contains(s.Substring(j, i - j)))
            {
                dp[i] = true;
                break; // No need to check other j values
            }
        }
    }
    
    return dp[s.Length];
}

Solution: Memoization (Top-Down)​

public bool WordBreak(string s, IList<string> wordDict)
{
    HashSet<string> dict = new HashSet<string>(wordDict);
    Dictionary<int, bool> memo = new Dictionary<int, bool>();
    return CanBreak(s, 0, dict, memo);
}

bool CanBreak(string s, int start, HashSet<string> dict, Dictionary<int, bool> memo)
{
    if (start == s.Length) return true;
    if (memo.ContainsKey(start)) return memo[start];
    
    for (int end = start + 1; end <= s.Length; end++)
    {
        string word = s.Substring(start, end - start);
        if (dict.Contains(word) && CanBreak(s, end, dict, memo))
        {
            memo[start] = true;
            return true;
        }
    }
    
    memo[start] = false;
    return false;
}

Word Break II (Return All Segmentations)​

LeetCode 140 | Difficulty: Hard​

Return all possible segmentations instead of just true/false.

public IList<string> WordBreakII(string s, IList<string> wordDict)
{
    Dictionary<string, List<string>> memo = new Dictionary<string, List<string>>();
    return Backtrack(s, new HashSet<string>(wordDict), memo);
}

List<string> Backtrack(string s, HashSet<string> dict, Dictionary<string, List<string>> memo)
{
    if (memo.ContainsKey(s)) return memo[s];
    
    List<string> result = new List<string>();
    
    if (s.Length == 0)
    {
        result.Add("");
        return result;
    }
    
    foreach (string word in dict)
    {
        if (s.StartsWith(word))
        {
            List<string> subResults = Backtrack(s.Substring(word.Length), dict, memo);
            foreach (string sub in subResults)
            {
                result.Add(word + (sub.Length == 0 ? "" : " " + sub));
            }
        }
    }
    
    memo[s] = result;
    return result;
}

Interview Tips​

  • Optimization: Use a HashSet for O(1) word lookups instead of iterating through the list
  • Early termination: Once dp[i] = true, break inner loop
  • Max word length optimization: Only check substrings up to the length of the longest word in the dictionary
  • BFS alternative: Think of it as finding a path from index 0 to index n
  • Common follow-up: Word Break II (return all possible sentences)